package sort.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @Description: 排序链表
 * @Author Stark
 * @Date 2022/3/20 8:53
 **/
public class Num148_SortList {
    //做法一：优先级队列
//    public ListNode sortList(ListNode head) {
//        Queue<ListNode> queue = new PriorityQueue<>(new Comparator<ListNode>() {
//            @Override
//            public int compare(ListNode o1, ListNode o2) {
//                return o1.val - o2.val;
//            }
//        });
//        while(head != null){
//            ListNode next = head.next;
//            head.next = null;
//            queue.offer(head);
//            head = next;
//        }
//        head = queue.poll();
//        ListNode cur = head;
//        while(!queue.isEmpty()){
//            cur = cur.next = queue.poll();
//        }
//        return head;
//    }

    //做法二:使用归并进行排序
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        return merge(head, null);
    }

    //需要注意何时断开结点之间的连接,否则会影响结果
    public static ListNode merge(ListNode head,ListNode tail){
        //当head的后一个结点是tail时
        //说明此时只有两个结点,断开彼此的连接,好用于后面的排序连接
        if(head.next == tail){
            head.next = null;
            return head;
        }
        ListNode slow = head,fast = head;
        while(fast != tail){
            fast = fast.next;
            slow = slow.next;
            if(fast != tail)
                fast = fast.next;
        }
        ListNode list1 = merge(head,slow);
        ListNode list2 = merge(slow,tail);
        return mergeHelper(list1,list2);
    }

    private static ListNode mergeHelper(ListNode head1, ListNode head2) {
        //用虚拟头结点进行连接
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while(head1 != null && head2 != null){
            if(head1.val <= head2.val ){
                cur.next = head1;
                head1 = head1.next;
            }else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        if(head1 != null){
            cur.next = head1;
        }
        if(head2 != null){
            cur.next = head2;
        }
        return dummyHead.next;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(3);
        ListNode node2 = new ListNode(1,node1);
        ListNode node3 = new ListNode(2,node2);
        ListNode node4 = new ListNode(4,node3);
        sortList(node4);
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

